/**
 * DpBase.java created by zhangzhidong 
 * at 下午10:35:43 2016年5月10日
 */
package algorithm.CIG.dp;

/**
 * @author zhangzhidong
 *
 */
public class DpBase {
	public static int [][] getPathArray(){
		return new int[][]{
			{1,3,5,9},
			{8,1,3,4},
			{5,0,6,1},
			{8,8,4,0}
		};
	}
	public static void main(String args[]){
		
		System.out.println(minPathSum2(getPathArray()));
	}
	public static int  minPathSum1(int m [][]){
		if(m==null || m.length==0 || m[0]==null|| m[0].length==0){
			return 0;
		}
		int row = m.length;
		int col = m[0].length;
		int [] [] dp = new int[row][col];
		dp[0][0] = m[0][0];
		for(int i = 1 ;i<row;i++){
			dp[i][0]=dp[i-1][0]+m[i][0];
		}
		for(int j = 1;j<col;j++){
			dp[0][j] = dp[0][j-1]+m[0][j];
		}
		for(int i = 1;i<row;i++){
			for(int j = 1;j<col;j++){
				dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+m[i][j];
			}
		}
		return dp[row-1][col-1];
	}
	
	public static int minPathSum2(int m[][]){
		if(m==null || m.length==0 || m[0]==null|| m[0].length==0){
			return 0;
		}
		int more = Math.max(m.length, m[0].length);
		int less = Math.min(m.length, m[0].length);
		//列比行多? m.length是指行 m[0].length是指列
		boolean colMore = more == m[0].length;
		int arr[] = new int [less];
		arr[0]=m[0][0];
		for(int i =1;i<less;i++){
			arr[i] = arr[i-1]+(colMore?m[i][0]:m[0][i]);
		}
		for(int j=1;j<more;j++){
			arr[0] = arr[0]+(colMore?m[0][j]:m[j][0]);
			for(int k = 1;k<less;k++){
				
				arr[k] = Math.min(arr[k-1], arr[k])+(colMore?m[k][j]:m[j][k]);
				
				
			}
		}
		
		
		return arr[less-1];
	}
	
}
